package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_077_Combinations {
    public static void main(String[] args) {

    }

    static class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> result = new ArrayList<>();

            if (n <= 0 || n < k)
                return result;

            ArrayList<Integer> item = new ArrayList<>();
            dfs(n, k, 1, item, result);

            return result;
        }

        private void dfs(int n, int k, int start, ArrayList<Integer> item, List<List<Integer>> res) {
            if (item.size() == k) {
                res.add(new ArrayList<>(item));
                return;
            }

            for (int i = start; i <= n; i++) {
                item.add(i);
                dfs(n, k, i + 1, item, res);
                item.remove(item.size() - 1);
            }
        }
    }
}
